/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 //===========================================
 //============暴力算法

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode * nodeA = headA;
        ListNode * nodeB = headB;
        while(nodeB)
        {
            while(nodeA)
            {
                if(nodeA == nodeB )
                    return nodeB;
                else 
                    nodeA = nodeA ->next;
            }
            nodeA = headA;
            nodeB = nodeB -> next;
        }
        return NULL;
    }
};
//通过	760 ms	14.8 MB


//===========================================
 //============
 //通过两个数组存储,从后向前 索引

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        vector<ListNode *> arrayA,arrayB;
        ListNode * nodeA = headA, *nodeB = headB;
        while(nodeA)
        {
            arrayA.push_back(nodeA);
            nodeA = nodeA -> next;
        }
            
        while(nodeB)
        {
            arrayB.push_back(nodeB);
            nodeB = nodeB -> next;
        }
            
        int i = arrayA.size(), j = arrayB.size();
        int res = -1;
        while(i>0&&j>0) 
        {
            if(arrayA[i-1] == arrayB[j-1])
            {
                res = i;
                i--;
                j--;
            }
            else
            {
                break;
            }
        }
        if(res == -1)
            return NULL;
        return arrayA[res-1];

    }
};
//通过	56 ms	17 MB


//===========================================
 //============
 //双指针法

 class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
       ListNode *pA = headA ,*pB = headB;
       int changeA = 0, changeB = 0;
       while(1)
       {
            if(pA == pB  && pA != NULL)
                return pA;
            if(pA)
                pA = pA ->next;
            if(pB)
                pB = pB ->next;
            if(pA == NULL && !changeA)
            {
                changeA = 1;
                pA =headB;
            }
            if(pB == NULL && !changeB)
            {
                changeB = 1;
                pB =headA;
            }
            if((changeB && pB == NULL)||(changeA && pA == NULL))
                break;
       }
       return NULL;

    }
};
//  执行用时：52 ms, 在所有 C++ 提交中击败91.79%的用户
// 内存消耗14.5 MB, 在所有 C++ 提交中击败了76.78%的用户